Markov chains are

• irreducible, i.e. every state can eventually be reached from any state;
• aperiodic, i.e. reverting to a state is not only possible after a multiple of a certain number of steps;
• positive recurrent, i.e. for all states, the expected number of transitions to return to that state is finite.

For such Markov Chains, transition probabilities converge to a unique stationary distribution on the state space.

Metropolis-Hastings is a class of MCMC methods.

• Propose \(Y\sim g(\cdot\mid X_t)\), compute \(\alpha(i,j)=\min\Bigl(1,\frac{f(j)\,g(i\mid j)}{f(i)\,g(j\mid i)}\Bigr)\).
• If \(U\le\alpha(i,j)\), move \(i\to j\); else stay at \(i\).
• Chain is reversible and has \(f\) as its stationary distribution.

The Gibbs sampler is an example of a Metropolis-Hastings algorithm.

• Sample \(Y\sim f(y\mid x)\), then \(X\sim f(x\mid y)\) each iteration.
• Defines a Markov chain on \((x,y)\) with joint \(f(x,y)\) as stationary law.
• Practical when full-conditionals \(f(x_j\mid x_{-j})\) are tractable.